package myself.a015Dp;


/**
 * @author 叶之越
 * Description
 * Date 2021/2/2
 * Time 14:11
 * Mail 739153436@qq.com
 */
public class CardsInLine {
    // 两个聪明绝顶的人之间的摸牌较量

    // 第一步：暴力递归
    // 由于是两个人之间的互相配合，那么应该需要两个递归
    public static int win1(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int first = f1(arr, 0, arr.length - 1);
        int second = g1(arr, 0, arr.length - 1);
        return Math.max(first, second);
    }


    private static int f1(int[] arr, int L, int R) {
        if (L == R) {
            return arr[L];
        }
        int l = arr[L] + g1(arr, L + 1, R);
        int r = arr[R] + g1(arr, L, R - 1);
        return Math.max(l, r);
    }

    private static int g1(int[] arr, int L, int R) {
        if (L == R) {
            return 0;
        }
        int l = f1(arr, L + 1, R);
        int r = f1(arr, L, R - 1);
        return Math.min(l, r);
    }


    // 第二步：傻白甜缓存
    // 先举例，看是否存在优化空间
    public static int win2(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int[][] arrF = new int[arr.length - 1][arr.length - 1];
        int[][] arrG = new int[arr.length - 1][arr.length - 1];
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length; j++) {
                arrF[i][j] = -1;
                arrG[i][j] = -1;
            }
        }
        int first = f2(arr, 0, arr.length - 1, arrF, arrG);
        int second = g2(arr, 0, arr.length - 1, arrF, arrG);
        return Math.max(first, second);
    }


    private static int f2(int[] arr, int L, int R, int[][] arrF, int[][] arrG) {
        if (arrF[L][R] != -1) {
            return arrF[L][R];
        }
        int ans = 0;
        if (L == R) {
            ans = arr[L];
        } else {
            int l = arr[L] + g2(arr, L + 1, R, arrF, arrG);
            int r = arr[R] + g2(arr, L, R - 1, arrF, arrG);
            ans = Math.max(l, r);
        }
        arrF[L][R] = ans;
        return ans;
    }

    private static int g2(int[] arr, int L, int R, int[][] arrF, int[][] arrG) {
        if (arrG[L][R] != -1) {
            return arrF[L][R];
        }
        int ans = 0;
        if (L == R) {
            ans = 0;
        } else {
            int l = f2(arr, L + 1, R, arrF, arrG);
            int r = f2(arr, L, R - 1, arrF, arrG);
            ans = Math.min(l, r);
        }
        arrG[L][R] = ans;
        return ans;
    }

    // 第三步：建立缓存表
    // 通过暴力递归函数逐步推断缓存表的关系
    public static int win3(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int[][] arrF = new int[arr.length - 1][arr.length - 1];
        int[][] arrG = new int[arr.length - 1][arr.length - 1];
        for (int i = 0; i < arr.length; i++) {
            arrF[i][i] = arr[i];
            arrG[i][i] = arr[i];
        }
        for (int L = 0; L < arr.length; L++) {
            for (int R = L + 1; R < arr.length; R++) {
                arrF[L][R] = Math.max(arr[L] + arrG[L + 1][R], arr[R] + arrG[L][R - 1]);
                arrG[L][R] = Math.min(arrG[L + 1][R], arrG[L][R - 1]);
            }
        }
        return Math.max(arrG[0][arr.length - 1], arrF[0][arr.length - 1]);
    }
}
